import java.util.ArrayList;
import java.util.Stack;

public class Main
{	
	public static void depthFirstSearch(int limit)
	{
		// nodurile care urmeaza sa fie expandate
		Stack<State> open = new Stack<State>();
		// nodurile deja expandate
		Stack<State> closed = new Stack<State>();
		// nodurile valide prin care s-a trecut
		Stack<State> states = new Stack<State>();
		
		Mal malStang = new Mal(0, 0, 0, 0);
		Mal malDrept = new Mal(1, 1, 1, 1);
		
		State s1 = new State(malStang, malDrept);
		boolean found = false;
		
		State temp;
		open.push(s1);
		states.push(s1);
		
		while (!open.empty())
		{
			temp = open.pop();
			closed.push(temp);
			
			if (temp.malStang.isFinal())
				break;
			if (closed.size() >= limit)
				break;
			
			ArrayList<State> tempArr = temp.expand();
			
			for (int i = 0; i < tempArr.size(); i++)
			{
				found = false;
				if (!tempArr.get(i).malStang.inConflict())
					if (!tempArr.get(i).malDrept.inConflict())
					{
						for (int j = 0; j < states.size(); j++)
							if (states.get(j).equals(tempArr.get(i)))
								found = true;
						if (!found)
						{
							open.add(0, tempArr.get(i));
							states.push(tempArr.get(i));
						}
					}
			}
		}
				
		System.out.println(closed);
	}
	
	public static void bidirectionalSearch()
	{
		// nodurile care urmeaza sa fie expandate
		Stack<State> open1 = new Stack<State>();
		// nodurile deja expandate
		Stack<State> closed1 = new Stack<State>();
		Stack<State> open2 = new Stack<State>();
		// nodurile deja expandate
		Stack<State> closed2 = new Stack<State>();
		// nodurile valide prin care s-a trecut
		Stack<State> states = new Stack<State>();
		
		Mal malStang = new Mal(0, 0, 0, 0);
		Mal malDrept = new Mal(1, 1, 1, 1);
		
		State s1 = new State(malStang, malDrept);
		boolean found = false;
		
		State temp1;
		State temp2;
		open1.push(s1);
		open2.push(new State(new Mal(1, 1, 1, 1), new Mal(0, 0, 0, 0)));
		states.push(s1);
		
		while (!open1.empty() && !open2.empty())
		{
			temp1 = open1.pop();
			temp2 = open2.pop();
			closed1.push(temp1);
			closed2.push(temp2);
			
			if (temp1.equals(temp2))
				break;
			
			ArrayList<State> tempArr1 = temp1.expand();
			ArrayList<State> tempArr2 = temp2.expand();
			
			for (int i = 0; i < tempArr1.size(); i++)
			{
				found = false;
				if (!tempArr1.get(i).malStang.inConflict())
					if (!tempArr1.get(i).malDrept.inConflict())
					{
						for (int j = 0; j < states.size(); j++)
							if (states.get(j).equals(tempArr1.get(i)))
								found = true;
						if (!found)
						{
							open1.add(0, tempArr1.get(i));
							states.push(tempArr1.get(i));
						}
					}
			}
			
			for (int i = 0; i < tempArr2.size(); i++)
			{
				found = false;
				if (!tempArr2.get(i).malStang.inConflict())
					if (!tempArr2.get(i).malDrept.inConflict())
					{
						for (int j = 0; j < states.size(); j++)
							if (states.get(j).equals(tempArr2.get(i)))
								found = true;
						if (!found)
						{
							open2.add(0, tempArr2.get(i));
							states.push(tempArr2.get(i));
						}
					}
			}
		}
		
		Stack<State> finall = new Stack<State>();
		for (int i = closed2.size() - 1; i >= 0; i--)
		{
			finall.add(closed2.get(i));
		}
		System.out.println(closed1 + " " + finall);
	}
	
	public static void depthFirstSearchWithLimit()
	{
		// nodurile care urmeaza sa fie expandate
		Stack<State> open = new Stack<State>();
		// nodurile deja expandate
		Stack<State> closed = new Stack<State>();
		// nodurile valide prin care s-a trecut
		Stack<State> states = new Stack<State>();
		
		Mal malStang = new Mal(0, 0, 0, 0);
		Mal malDrept = new Mal(1, 1, 1, 1);
		
		State s1 = new State(malStang, malDrept);
		boolean found = false;
		
		State temp;
		open.push(s1);
		states.push(s1);
		
		while (!open.empty())
		{
			temp = open.pop();
			closed.push(temp);
			
			if (temp.malStang.isFinal())
				break;
			
			ArrayList<State> tempArr = temp.expand();
			
			for (int i = 0; i < tempArr.size(); i++)
			{
				found = false;
				if (!tempArr.get(i).malStang.inConflict())
					if (!tempArr.get(i).malDrept.inConflict())
					{
						for (int j = 0; j < states.size(); j++)
							if (states.get(j).equals(tempArr.get(i)))
								found = true;
						if (!found)
						{
							open.add(0, tempArr.get(i));
							states.push(tempArr.get(i));
						}
					}
			}
		}
		
		for (int i = 0; i < 4; i++)
			closed.remove(i);
		
		System.out.println(closed);
	}
	
	public static void depthFirstSearch()
	{
		// nodurile care urmeaza sa fie expandate
		Stack<State> open = new Stack<State>();
		// nodurile deja expandate
		Stack<State> closed = new Stack<State>();
		// nodurile valide prin care s-a trecut
		Stack<State> states = new Stack<State>();
		
		Mal malStang = new Mal(0, 0, 0, 0);
		Mal malDrept = new Mal(1, 1, 1, 1);
		
		State s1 = new State(malStang, malDrept);
		boolean found = false;
		
		State temp;
		open.push(s1);
		states.push(s1);
		
		while (!open.empty())
		{
			temp = open.pop();
			closed.push(temp);
			
			if (temp.malStang.isFinal())
				break;
			
			ArrayList<State> tempArr = temp.expand();
			
			for (int i = 0; i < tempArr.size(); i++)
			{
				found = false;
				if (!tempArr.get(i).malStang.inConflict())
					if (!tempArr.get(i).malDrept.inConflict())
					{
						for (int j = 0; j < states.size(); j++)
							if (states.get(j).equals(tempArr.get(i)))
								found = true;
						if (!found)
						{
							open.add(0, tempArr.get(i));
							states.push(tempArr.get(i));
						}
					}
			}
		}
		
		System.out.println(closed);
	}

	public static void breadthFirstSearch()
	{
		// nodurile care urmeaza sa fie expandate
		Stack<State> open = new Stack<State>();
		// nodurile deja expandate
		Stack<State> closed = new Stack<State>();
		// nodurile valide prin care s-a trecut
		Stack<State> states = new Stack<State>();
		
		Mal malStang = new Mal(0, 0, 0, 0);
		Mal malDrept = new Mal(1, 1, 1, 1);
		
		State s1 = new State(malStang, malDrept);
		boolean found = false;
		
		State temp;
		open.push(s1);
		states.push(s1);
		
		while (!open.empty())
		{
			temp = open.pop();
			closed.push(temp);
			
			if (temp.malStang.isFinal())
				break;
			
			ArrayList<State> tempArr = temp.expand();
			
			for (int i = 0; i < tempArr.size(); i++)
			{
				found = false;
				if (!tempArr.get(i).malStang.inConflict())
					if (!tempArr.get(i).malDrept.inConflict())
					{
						for (int j = 0; j < states.size(); j++)
							if (states.get(j).equals(tempArr.get(i)))
								found = true;
						if (!found)
						{
							open.push(tempArr.get(i));
							states.push(tempArr.get(i));
						}
					}
			}
		}
		
		System.out.println(closed);
	}

	public static void main(String[] args)
	{
		//bidirectionalSearch();
		depthFirstSearch();
		depthFirstSearch(5);
		depthFirstSearchWithLimit();
		breadthFirstSearch();
	}
}
